package leetcode_1_200;

public class LeeCode_42 {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
    private static int trap(int[] height) {
        int n = height.length, max = 0, diff = 0, index = -1, ans = 0;
        for (int i = 0; i < n; i++) {
            if (height[i] >= max){
                ans += max * (i - index - 1) - diff;
                max = height[i];
                diff = 0;
                index = i;
            }else {
                diff += height[i];
            }
        }
        int mid = index;
        max = 0;
        diff = 0;
        index = n;
        for (int i = n - 1;i >= mid;i--){
            if (height[i] > max){
                ans += max * (index - i - 1) - diff;
                max = height[i];
                diff = 0;
                index = i;
            }else {
                diff += height[i];
            }
        }
        return ans;
    }
}
